package com.yun.algorithm.string;

import java.util.Arrays;

public class ZFunction {

    public static void main(String[] args) {
        ZFunction obj = new ZFunction();
        String s = "ABABAB";
        obj.zF(s);
    }

    public int[] zF(String s) {
        char[] sCharArray = s.toCharArray();
        int[] z = new int[s.length()];
        int l = 0, r = 0;
        z[0] = s.length();
        for (int i = 1; i < s.length(); i++) {
            if(z[i - l] < r - i){
                z[i] = z[i - l];
            }else {
                if(i<=r){
                    z[i] = r - i;
                }
                while (i + z[i] < s.length() && sCharArray[z[i]] == sCharArray[i + z[i]]) {
                    z[i]++;
                }
                l = i;
                r = i + z[i] - 1;
            }
        }
        return z;
    }
}
